﻿using System;
using System.Collections.Generic;
using System.Text;
using UnityEngine;


public class Class3 : MonoBehaviour
{
    public Transform StartPoint;
    public Transform EndPoint;
    public GameObject Root;
    public float size = 5f;
    public float height = .5f;
    private string startObj = string.Empty;
    private string endObj = string.Empty;
    MeshData baseDate = null;
    void Start()
    {
        DrawSample(size, StartPoint.position, EndPoint.position, Root);
        print(SystemInfo.graphicsDeviceName + "," + SystemInfo.graphicsDeviceVendor + "," + SystemInfo.graphicsMemorySize);
    }
    void OnGUI()
    {
        GUILayout.Label("start:");
        startObj = GUILayout.TextField(startObj);
        GUILayout.Label("end:");
        endObj = GUILayout.TextField(endObj);
        if (GUILayout.Button("OK"))
        {
            string[] spos = startObj.Split(new char[] { ',' });
            int fX = int.Parse(spos[0]);
            int fY = int.Parse(spos[1]);
            spos = endObj.Split(new char[] { ',' });
            int tX = int.Parse(spos[0]);
            int tY = int.Parse(spos[1]);

            List<MeshNode> PathList = CalculatePath(baseDate, fX, fY, tX, tY);
            
            //print(current.TopLeft.F);
        }
    }
    List<MeshNode> CalculatePath(MeshData data, int fX, int fY, int tX, int tY)
    {
        List<MeshNode> pathList = new List<MeshNode>();
        if ((fX == tX && fY == tY) || fX >= data.XCount || fY >= data.YCount || tX >= data.XCount || tY >= data.YCount || data.Data[fX, fY] == null || data.Data[tX, tY] == null) return pathList;

        data.Data[fX, fY].F = 0;
        data.Data[fX, fY].G = 0;
        data.Data[fX, fY].H = 0;
        data.AddToOpenList(data.Data[fX, fY]);
        while (data.OpenListLength > 0)
        {
            MeshNode current = data.OpenList[data.OpenListStart];
            data.RemoveOpenList();
            data.AddToCloseList(current);
            if (CalculateMeshNode(data, current, tX, tY))
            {
                pathList.Add(current);
                current.Obj.transform.position += Vector3.up * 10;
                while (current.Parent != null)
                {
                    current = current.Parent;
                    pathList.Add(current);
                    current.Obj.transform.position += Vector3.up * 10;
                }
                break;
            }
        }
        return pathList;
    }
    bool CalculateMeshNode(MeshData data, MeshNode mesh, int tX, int tY)
    {
        bool hasTop = false, hasLeft = false, hasRight = false, hasBottom = false, tmp = false;
        if (CalculateMeshNode(data, mesh, mesh.TopCenter, mesh.G + 10, tX, tY, ref hasTop)) return true;
        if (CalculateMeshNode(data, mesh, mesh.Left, mesh.G + 10, tX, tY, ref hasLeft)) return true;
        if (CalculateMeshNode(data, mesh, mesh.Right, mesh.G + 10, tX, tY, ref hasRight)) return true;
        if (CalculateMeshNode(data, mesh, mesh.BottomCenter, mesh.G + 10, tX, tY, ref hasBottom)) return true;
        if (hasTop && hasLeft && CalculateMeshNode(data, mesh, mesh.TopLeft, mesh.G + 14, tX, tY, ref tmp)) return true;
        if (hasTop && hasRight && CalculateMeshNode(data, mesh, mesh.TopRight, mesh.G + 14, tX, tY, ref tmp)) return true;
        if (hasBottom && hasLeft && CalculateMeshNode(data, mesh, mesh.BottomLeft, mesh.G + 14, tX, tY, ref tmp)) return true;
        if (hasBottom && hasRight && CalculateMeshNode(data, mesh, mesh.BottomRight, mesh.G + 14, tX, tY, ref tmp)) return true;
        return false;
    }
    bool CalculateMeshNode(MeshData date, MeshNode current, MeshNode child, int G, int tX, int tY, ref bool hasThis)
    {
        if (child != null)
        {
            if (!child.Enable) return false;
            hasThis = true;
            for (int i = 0; i < date.CloseListLength; i++)
            {
                if (child.X == date.CloseList[i].X && child.Y == date.CloseList[i].Y) return false;
            }
            MeshNode findNode = null;
            int index = 0;
            for (int i = date.OpenListStart; i < date.OpenListEnd; i++)
            {
                if (child.X == date.OpenList[i].X && child.Y == date.OpenList[i].Y)
                {
                    findNode = date.OpenList[i];
                    index = i;
                    break;
                }
            }
            if (findNode != null)
            {
                if (G < findNode.G)
                {
                    findNode.Parent = current;
                    date.ReOrder(G, index);
                }
            }
            else
            {
                if (child.X == tX && child.Y == tY) return true;
                else
                {
                    child.H = Math.Abs(tX - child.X) * 10 + Math.Abs(tY - child.Y) * 10;
                    child.G = G;
                    child.F = child.H + child.G;
                    child.Parent = current;
                    date.AddToOpenList(child);
                }
            }
        }
        return false;
    }
    void DrawSample(float oSize, Vector3 start, Vector3 end, GameObject obj)
    {
        Vector3 result = end - start;
        int xCount = (int)(result.x / size);
        int yCount = (int)(result.z / size);
        bool xOk = false, yOk = false;
        Vector3 pos = Vector3.zero;
        baseDate = new MeshData(xCount, yCount);
        for (int i = 0; i < xCount; i++)
        {
            for (int j = 0; j < yCount; j++)
            {
                xOk = yOk = false;
                pos.x = start.x + i * size;
                pos.z = start.z + j * size;
                pos.y = Terrain.activeTerrain.SampleHeight(pos);
                if (!Physics.CheckSphere(pos + Vector3.up * 0.5f * size, 0.49f * size))
                {
                    MeshNode mesh = new MeshNode();
                    baseDate.Data[i, j] = mesh;
                    mesh.X = i;
                    mesh.Y = j;
                    mesh.Pos = pos;
                    mesh.Obj = GameObject.Instantiate(obj, pos, Quaternion.identity) as GameObject;
                    mesh.Obj.name = i + "," + j;
                }
            }
        }
        SetNodeRelation(baseDate);
    }
    void SetNodeRelation(MeshData data)
    {
        for (int i = 0; i < data.XCount; i++)
        {
            for (int j = 0; j < data.YCount; j++)
            {
                if (baseDate.Data[i, j] != null)
                {
                    if (i > 0)
                    {
                        if (baseDate.Data[i - 1, j] != null) baseDate.Data[i, j].Left = baseDate.Data[i - 1, j];
                        if (j > 0) if (baseDate.Data[i - 1, j - 1] != null) baseDate.Data[i, j].BottomLeft = baseDate.Data[i - 1, j - 1];
                    }
                    if (i < data.XCount - 1)
                    {
                        if (baseDate.Data[i + 1, j] != null) baseDate.Data[i, j].Right = baseDate.Data[i + 1, j];
                        if (j < data.YCount - 1) if (baseDate.Data[i + 1, j + 1] != null) baseDate.Data[i, j].TopRight = baseDate.Data[i + 1, j + 1];
                    }
                    if (j > 0)
                    {
                        if (baseDate.Data[i, j - 1] != null) baseDate.Data[i, j].BottomCenter = baseDate.Data[i, j - 1];
                        if (i < data.XCount - 1) if (baseDate.Data[i + 1, j - 1] != null) baseDate.Data[i, j].BottomRight = baseDate.Data[i + 1, j - 1];
                    }
                    if (j < data.YCount - 1)
                    {
                        if (baseDate.Data[i, j + 1] != null) baseDate.Data[i, j].TopCenter = baseDate.Data[i, j + 1];
                        if (i > 0) if (baseDate.Data[i - 1, j + 1] != null) baseDate.Data[i, j].TopLeft = baseDate.Data[i - 1, j + 1];
                    }
                }
            }
        }
    } 
}
[Serializable]
public class MeshData
{
    public MeshNode[,] Data;
    public int XCount;
    public int YCount;
    public MeshData(int xCount, int yCount)
    {
        XCount = xCount;
        YCount = yCount;
        Data = new MeshNode[XCount, YCount];
        OpenList = new MeshNode[XCount * YCount];
        CloseList = new MeshNode[OpenList.Length];
        ResetAllList();
    }
    public int OpenListEnd;
    public int OpenListStart;

    public int OpenListLength;
    public int CloseListLength;
    public MeshNode[] OpenList;
    public MeshNode[] CloseList;
    public void AddToOpenList(MeshNode node)
    {
        OpenList[OpenListEnd] = node;
        OpenListEnd++;
        OpenListLength++;
        OrderList(OpenList, OpenListStart, OpenListEnd - 1);
    }
    public void ReOrder(int G, int index)
    {
        OpenList[index].G = G;
        OpenList[index].F = OpenList[index].G + OpenList[index].H;
        OrderList(OpenList, OpenListStart, index);
    }
    public void RemoveOpenList()
    {
        OpenListStart++;
        OpenListLength--;
    }

    public void AddToCloseList(MeshNode node)
    {
        CloseList[CloseListLength] = node;
        CloseListLength++;
    }
    public void ResetAllList()
    {
        OpenListEnd = OpenListStart = CloseListLength = 0;
    }
    void OrderList(MeshNode[] list, int start, int end)
    {
        if (OpenListLength > 1)
        {
            MeshNode tmp = null;
            for (int i = end; i > start; i--)
            {
                if (list[i].F < list[i - 1].F)
                {
                    tmp = list[i];
                    list[i] = list[i - 1];
                    list[i - 1] = tmp;
                }
                else break;
            }
        }
    }
}
[Serializable]
public class MeshNode
{
    public int F;
    public int G;
    public int H;
    public Vector3 Pos;
    public MeshNode Parent;
    public GameObject Obj;
    public int X;
    public int Y;
    public bool Enable = true;

    public MeshNode TopLeft;
    public MeshNode TopCenter;
    public MeshNode TopRight;
    public MeshNode Left;
    public MeshNode Right;
    public MeshNode BottomLeft;
    public MeshNode BottomCenter;
    public MeshNode BottomRight;
}

